package zifuchuan.zifuchuanpipei;

public class _02RabinKarp {
    public static void main(String[] args) {
        String s = "ABABABA";
        String p = "ABA";
        match(p, s);
    }

    private static void match(String p, String s) {
        long hash_p = hash(p);//p的hash值
        long[] hashOfS = hash(s, p.length());
        match(hash_p, hashOfS);
    }

    private static void match(long hash_p, long[] hash_s) {
        for (int i = 0; i < hash_s.length; i++) {
            if (hash_s[i] == hash_p) {
                System.out.println("match:" + i);
            }
        }
    }

    final static long seed = 31;
    /**
     * n是子串的长度
     * 用滚动方法求出s中长度为n的每个子串的hash,组成一个hash数组
     */
    static long[] hash(final String s, final int n) {
        long[] res = new long[s.length() - n + 1];
        //前m个字符的hash
        res[0] = hash(s.substring(0, n));
        for (int i = n; i < s.length(); i++) {
            char newChar = s.charAt(i);
            char ochar = s.charAt(i - n);
            //前n个字符的hash*seed-前n字符的第一字符*seed的n次方
            long v = (res[i - n] * seed + newChar - digui._06求a的n次幂.ex2(seed, n) * ochar) % Long.MAX_VALUE;
            res[i - n + 1] = v;
        }
        return res;
    }

    static long hash(String str) {
        long h = 0;
        for (int i = 0; i != str.length(); ++i) {
            h = seed * h + str.charAt(i);
        }
        return h % Long.MAX_VALUE;
    }
}
